# -*- coding: utf-8 -*-
"""
-------------------------------------------------
   File Name：     utils
   Description :
   Author :       Flyoung
   date：          2023/4/16
-------------------------------------------------
   Change Activity:
                   2023/4/16:
-------------------------------------------------
"""
from typing import Union

from data_structure.non_terminator import NonTerminator
from data_structure.grammar import Grammar
from data_structure.string import String
from lib import epsilon, eof
import pandas as pd


def eliminate_direct_left_recursion(g: Grammar) -> list[NonTerminator]:
    # 消除直接左递归
    non_terminator_list: list[NonTerminator] = list()
    for non_terminator in g.non_terminator_list:
        # 左递归的串
        left_recursion_string = [
            i for i in non_terminator.equal_list
            if i.get_first_symbol() == non_terminator.name
        ]
        # 若存在左递归的串
        if len(left_recursion_string) > 0:
            # 非左递归的串
            non_left_recursion_string = [
                i for i in non_terminator.equal_list
                if i.get_first_symbol() != non_terminator.name
            ]
            # 新非终结符
            new_non_terminator_name = non_terminator.name.content + "'"
            # 将当前非终结符分解为 2 部分
            # 1. 非终结符 -> 推出新非终结符
            non_terminator_ = NonTerminator(non_terminator.name)
            non_terminator_.equal_list = [i + String(new_non_terminator_name) for i in non_left_recursion_string]
            non_terminator_list.append(non_terminator_)
            # 2. 新非终结符 -> 左递归部分的右侧

            new_non_terminator = NonTerminator(String(new_non_terminator_name))
            new_non_terminator.equal_list.extend([
                String(i.content[1:]) + String(new_non_terminator_name)
                for i in left_recursion_string
            ])
            new_non_terminator.equal_list.append(String(epsilon))
            non_terminator_list.append(new_non_terminator)
        else:
            non_terminator_list.append(non_terminator)

    return non_terminator_list


def indirect_left_recursion_to_direct_left_recursion(g: Grammar) -> list[NonTerminator]:
    """
    将【间接左递归】转化为【直接左递归】
    :param g:
    :return:
    """
    non_terminator_list: list[NonTerminator] = list()
    for i, non_terminator_i in enumerate(g.non_terminator_list):
        non_terminator_list.append(non_terminator_i)
        # 检查在非终结符 i 之前出现的非终结符 j，是否会导致 i 间接左递归
        # j -> i??
        # i -> j
        for j in range(0, i):
            non_terminator_j = g.non_terminator_list[j]
            # 间接左递归的串
            indirect_left_string = [
                s for s in non_terminator_i.equal_list
                if s.get_first_symbol() == non_terminator_j.name
            ]
            # 存在间接左递归
            if len(indirect_left_string) > 0:
                # 非左递归的串
                non_left_recursion_string = [
                    s for s in non_terminator_i.equal_list
                    if s.get_first_symbol() != non_terminator_j.name
                ]
                # 消除间接左递归后的 i
                new_non_terminator_i = NonTerminator(non_terminator_i.name)
                new_non_terminator_i.equal_list.extend(non_left_recursion_string)
                # 将所有间接左递归的部分，替换成直接左递归
                for string_i in indirect_left_string:
                    for string_j in non_terminator_j.equal_list:
                        new_non_terminator_i.equal_list.append(
                            string_j + String(string_i.content[1:])
                        )
                non_terminator_list.append(new_non_terminator_i)
                # 移除发生间接左递归的 i
                non_terminator_list.remove(non_terminator_i)

    return non_terminator_list


def eliminate_left_recursion(g: Grammar, show_info: bool = True) -> None:
    """
    消除左递归
    :param g: 文法
    :param show_info: 是否打印消除左递归后的产生式
    :return:
    """
    # 1. 间接左递归转化为直接左递归
    g.non_terminator_list = indirect_left_recursion_to_direct_left_recursion(g)
    # 2. 消除直接左递归
    g.non_terminator_list = eliminate_direct_left_recursion(g)
    # 打印信息
    if show_info:
        g.show_non_terminator_list()


def get_first(g: Grammar, non_terminator: NonTerminator) -> set[String]:
    """
    获取文法 g 中非终结符 non_terminator 的 First 集合
    :param g:
    :param non_terminator:
    :return:
    """
    first_set: set[String] = set()
    for right in non_terminator.equal_list:
        if not g.is_non_terminator(right.get_first_symbol()):
            first_set.add(String(right.get_first_symbol()))
        else:
            first_set.update(
                get_first(g, g.get_non_terminator(right.get_first_symbol()))
            )
    return first_set


def solve_first(g: Grammar) -> None:
    """
    求解文法 g 的 first 集合
    :param g:
    :return:
    """
    non_terminator_list = g.non_terminator_list
    for non_terminator in non_terminator_list:
        non_terminator.First = get_first(g, non_terminator)


def solve_follow(g: Grammar) -> None:
    """
    求解文法 g 的 follow 集合
    :param g:
    :return:
    """
    while True:
        make_change = False
        for non_terminator in g.non_terminator_list:
            # 1. 产生式左侧非终结符添加文本结束符
            if non_terminator.update_follow_set({String(eof)}):
                make_change = True

            for right in non_terminator.equal_list:
                # 末尾符号
                last = right.get_last_symbol()
                if g.is_non_terminator(last):
                    last_non_terminator = g.get_non_terminator(last)

                    # 2. Follow(产生式左侧) 添加到 Follow(产生式末尾的非终结符)
                    if last_non_terminator.update_follow_set(non_terminator.Follow):
                        make_change = True

                    # 3. S -> AB，B 可以推出 epsilon，将 Follow(S) 添加到 Follow(A)
                    penultimate = right.get_penultimate_symbol()
                    penultimate_non_terminator = g.get_non_terminator(penultimate)
                    if last_non_terminator.is_derive_epsilon():
                        # 倒数第二个符号，即 S -> AB 中的 A
                        if g.is_non_terminator(penultimate):

                            if penultimate_non_terminator.update_follow_set(non_terminator.Follow):
                                make_change = True

                    # 4. 将 First(B) 加入 Follow(A)
                    if g.is_non_terminator(penultimate):
                        if penultimate_non_terminator.update_follow_set(last_non_terminator.First):
                            make_change = True

                # 5. 非终结符右侧出现终结符
                right_symbols = right.split_symbol()
                for i, symbol in enumerate(right_symbols):
                    if i + 1 < len(right.split_symbol()):
                        if g.is_non_terminator(right_symbols[i]) and not g.is_non_terminator(right_symbols[i + 1]):
                            if g.get_non_terminator(right_symbols[i]).update_follow_set({right_symbols[i + 1]}):
                                make_change = True
        if not make_change:
            break


def construction_prediction_analysis_table(g: Grammar) -> pd.DataFrame:
    """
    构造预测分析表
    :param g:
    :return:
    """
    column_names = ['non-terminator'] + list(g.get_input_symbols())
    df = pd.DataFrame(columns=column_names)

    for non_terminator in g.non_terminator_list:
        row = {column_name: None for column_name in column_names}
        row['non-terminator'] = non_terminator.name
        for right in non_terminator.equal_list:
            # 非终结符若推导出 epsilon，则对应列为 Follow 集合
            if right == epsilon:
                follow = non_terminator.Follow
                for symbol in follow:
                    non_terminator_ = NonTerminator(non_terminator.name)
                    non_terminator_.equal_list.append(right)
                    # todo ：非终结符对应的输入符号，产生式有可能为多个
                    if row[symbol] is None:
                        row[symbol] = non_terminator_
            else:
                first_symbol = right.get_first_symbol()
                # 产生式右侧的起始符号为非终结符，则 select 集合为起始符号的 First 集合
                if g.is_non_terminator(first_symbol):
                    first = g.get_non_terminator(first_symbol).First
                    for symbol in first:
                        non_terminator_ = NonTerminator(non_terminator.name)
                        non_terminator_.equal_list.append(right)
                        row[symbol] = non_terminator_
                # 产生式右侧的起始符号为终结符，则 select 集合为该终结符
                else:
                    non_terminator_ = NonTerminator(non_terminator.name)
                    non_terminator_.equal_list.append(right)
                    row[first_symbol] = non_terminator_
        df = df.append(row, ignore_index=True)
    print(df)
    return df


def predictive_analysis(g: Grammar, start_symbol: str, input_string: str):
    """
    根据文法 g 对输入字符串 input_string 进行预测分析
    :param g: 文法
    :param start_symbol: 起始符号
    :param input_string: 输入字符串
    :return:
    """
    prediction_analysis_table = construction_prediction_analysis_table(g)

    def handle_reject_case():
        # 拒绝输入字符串
        print('reject')
        pass

    # 栈
    stack = [eof, start_symbol]
    # 输入
    queue = [i for i in String(input_string.replace(' ', '')).split_symbol()] + [eof]
    column_names = ['stack', 'input', 'action']
    # 分析过程
    analysis_process = pd.DataFrame(columns=column_names)
    while len(stack) > 0:
        df_new_row = {column_name: None for column_name in column_names}
        top = stack[-1]
        front = queue[0]
        df_new_row['stack'] = ''.join(stack)
        df_new_row['input'] = ''.join(queue)
        # 栈顶为非终结符
        if g.is_non_terminator(top):
            reject = True
            column_values = prediction_analysis_table['non-terminator']
            # 预测分析表中 top 行 front 列对应的产生式
            for row_idx, column_value in enumerate(column_values):
                if column_value.content == top:
                    row_values = prediction_analysis_table.loc[row_idx]
                    production: Union[None, NonTerminator] = row_values[front]
                    # 若对应产生式为空，则拒绝该输入串
                    if production is None:
                        reject = True
                        break
                    else:
                        reject = False
                        df_new_row['action'] = production.__str__()
                        stack.pop()
                        right = [i.content for i in production.equal_list]
                        right = String(''.join(right)).split_symbol()
                        if epsilon in right:
                            right.remove(epsilon)
                        stack.extend(right[::-1])
            if reject:
                handle_reject_case()
                break
        else:
            # 栈顶的终结符与输入字符串队头相等，匹配成功
            if top == front:
                stack.pop()
                queue.pop(0)
                df_new_row['action'] = f'match {front}'
            else:
                handle_reject_case()
                break

        analysis_process = analysis_process.append(df_new_row, ignore_index=True)

    print(analysis_process)
